/*
Given a line, adjust this line to the page width.

For example, given "Dog is cute" (length of chars is 11) and the page width is 15, adjust the line to "Dog is cute". The extra spaces should be distributed as much even as possible. Assume there is no space before the first word or after the last word.
*/

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

vector<string> alignPage(const string &str, int width)
{
    vector<string> ans;
    vector<string> cur;
    vector<string> input;
    istringstream iss(str);
    string s;
    int len = 0, i = 0, count = 0;
    while(iss >> s) {
       cout << s << endl;
       input.push_back(s); 
    }
    while(i < input.size()) {
        if (len + count + input[i].size() < width) {
	    len += input[i].size();
            cur.push_back(input[i]);
            count++;
            i++;
	} else if (len + count + input[i].size() == width) {
	    string out;
	    for (int j = 0; j < cur.size(); j++) {
		out += cur[j] + " ";	
	    }
	    out += input[i];
	    ans.push_back(out);
	    cur.clear();
	    i++;
	    len = 0;
	    count = 0;
	} else  {
	    string out;
            int padding = count == 1 ? (width - len) : (width - len)/(count-1);
	    int lastPadding = count == 1 ? 0 : padding + (width - len)%(count-1);
	    cout << padding << " " << lastPadding << endl;
	    for (int j = 0; j < max(1,int(cur.size()-1)); j++) {
                cout << out << endl;
		out += cur[j] + (j == cur.size()-2 ? string(lastPadding, ' ') :string(padding, ' '));
	    }
            out += cur[cur.size()-1];
	    ans.push_back(out);
	    cur.clear();
	    count = 0;
	    len = 0;
	}
	if (i == input.size()) {
	    string out;
            int padding = count == 1 ? (width - len) : (width - len)/(count-1);
	    int lastPadding = count == 1 ? 0 : padding + (width - len)%(count-1);
	    cout << padding << " " << lastPadding << endl;
	    for (int j = 0; j < max(1,int(cur.size()-1)); j++) {
                cout << out << endl;
		out += cur[j] + (j == cur.size()-2 ? string(lastPadding, ' ') :string(padding, ' '));
	    }
            out += cur[cur.size()-1];
	    ans.push_back(out);
	}
    }
    
    return ans;
}


int main(int argc, char **argv)
{
    vector<string> ans = alignPage("Dog is fucking cute", 7);
    for (int i = 0; i < ans.size(); i++) 
	cout << ans[i] << endl;
}
